package xyz.naokeziteng.data_structure.graph_theory;

/**
 * @author hawk
 * @date 2022/10/8
 * @desc 环检测
 **/
public class DfsRingCheck {

    private Graph G;
    private boolean[] visited;

    //是否有环
    private boolean hasRing;

    /**
     * @param G 图
     */
    public DfsRingCheck(Graph G) {
        this.G = G;
        this.hasRing = false;
        this.visited = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                if (dfs(v, v)) {
                    hasRing = true;
                    break;
                }
            }
        }
    }

    //从顶点V开始，判断图中是否有环
    private boolean dfs(int v, int parent) {
        visited[v] = true;
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                if (dfs(w, v)) {
                    return false;
                }
            } else if (w != parent) {
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        DfsRingCheck g1 = new DfsRingCheck(new Graph("src/main/resources/g.txt"));
        System.out.println(g1.hasRing);
        DfsRingCheck g2 = new DfsRingCheck(new Graph("src/main/resources/g2.txt"));
        System.out.println(g2.hasRing);
    }
}
